/**
 * First class functions.
 * 
 * (The most experimental part of the immutable collections library.) 
 * 
 * ## Functions
 * 
 * Functions of one argument are represented by instances of `Function1`.
 * Functions of two arguments are represented by instances of `Function2` and so on up to `Function5`. After that
 * there is a `FunctionN` which can handle an arbitrary number of arguments but provides (even) less type safety.
 * 
 * There is no way to represent a function that does not have any arguments. In functional languages, a function with
 * no arguments is just a constant. That is not quite true of Java of course but let's pretend.
 * 
 * The only way to create a function is to "extract" one from an existing class using a `FnFactory` object.
 * 
 * In this example we create a {@link FnFactory} object on the `Object` class and then get the function with one argument
 * called `toString()` which returns an object of type `String`:
 * 
 *     Function1<String> fn = FnFactory.on(Object.class).getFn(String.class, "toString");
 *     fn.toString()  => "Object#toString :: Object -> String"
 * 
 * The toString method shows the method that the function was extracted from `Object#toString` - and then an indication that
 * it takes an `Object` argument and returns a `String` result.
 * 
 * Note that the instance method `toString()` has no arguments - but when it is used as a function it has one argument
 * - the string instance it will be applied to.
 * 
 * To invoke the function we use `invoke()`:
 * 
 *     fn.invoke(1)  =>  "1"
 * 
 * Let's consider an example of a function with two arguments. Let's create a function that concatenates two `Strings` by
 * extracting it from the `concat()` method of the `String` class:
 * 
 *     Function2<String> fn2 = FnFactory.on(String.class).getFn(String.class, "concat", String.class);
 *     fn2.toString()  =>  "String#concat :: String -> String -> String"
 *     
 * The string representation of this function may not seem obvious at first sight. The section on Currying below
 * will explain all.
 *     
 * The order of the arguments to `getFn()` reflect the way that the method we are extracting is declared in Java:
 * 
 *     getFn(    String.class,   "concat",   String.class         )
 *               |                |          |
 *     public    String           concat (   String            str)
 * 
 * In order to invoke it directly we use `invoke()` twice:
 * 
 *     fn2.invoke("hello ").invoke("there")  =>  "hello there"
 * 
 * It might not seem obvious why we use two calls to `invoke()` instead of one with two arguments - see the section on
 * currying below for an explanation.
 * 
 * In fact you won't normally be using `invoke()` directly. The point of having functions as first class objects is that they can
 * be passed as arguments to other java methods that will invoke the functions themselves.
 * 
 * Examples of methods that take functions as arguments in this library are `map()` and `fold()`.
 * 
 * ### Methods with variable numbers of arguments
 * 
 * You can extract a function based on a Java method whose last argument is an array. If the method is invoked with
 * a last argument that is not already an array, it will get wrapped in an array of the appropriate type.
 * 
 * This allows you to use such methods relatively easily:
 * 
 *     Function2<String> fn = FnFactory.on(String.class).getFnStatic( //
 *             String.class, "format", String.class, new Object[] {}.getClass());
 * 
 *     ImList.onArray(1.3, 5.8, 13.21).map(fn.invoke("%e")  =>  [1.300000e+00, 5.800000e+00, 1.321000e+01]
 * 
 * 
 * ## The map() method
 * 
 * Let's convert a list of strings to upper case.
 * 
 * First we need a function that will take one 
 * `String` argument and return an upper case version of it.
 * 
 * We extract the `upperCase()` instance function from the String class:
 * 
 *     Function1<String> fn = FnFactory.on(String.class).getFn(String.class, "toUpperCase");
 *
 * now let's run the map method with this function as the argument.
 * 
 *       ImList.onArray("hello", " ", "there").map(fn)  => ["HELLO", " ", "THERE"]
 *       
 * The `map()` function applies the function it is given to to each element of the list in turn, creating a new list.
 * 
 * All of the subclasses of `ImCollection` and `ImRoseTre`e implement the map method. For the two set classes, the number
 * of elements in the resulting set may be smaller than the original set.
 * 
 * ## The fold() method
 * 
 * This method combines the elements of `this` using the function `fn`, starting with `start`.
 * 
 *     public <O> O fold(O start, Function2<O> fn)
 * 
 * `fold` is what functional languages often call `foldl`.
 *    
 * `fold` applies the two-argument function `fn` to `start` and the first element of `this` to get a value `v1`.
 *  
 *     v1 = fn(start, list.at(1))
 *      
 * It then applies `fn` to `v1` and the second element to get a value v2.
 *  
 *     v2 = fn(v1, list.at(2))
 *  
 * It carries on in this fashion until it reaches the end:
 *  
 *     v1 = fn(start, list.at(1))
 *     v2 = fn(v1, list.at(2))
 *     v3 = fn(v2, list.at(3))
 *     ...
 *     vn = fn(vn-1, list.at(n))
 *  
 * The result is the last value obtained.
 *  
 * Another way of visualising this is to imagine that the two argument function `fn` is the `*` operator. Then
 * the invocation of `fn` on arguments `a` and `b` can be written:
 *  
 *      a * b
 *  
 * With this convention, we have (using `ImList` as an example):
 *  
 *      ImList.on(a, b, c).fold(start, fn)   =>  ((start * a) * b) * c
 *  
 * ### The 'nth element'
 *  
 * In the above, the *nth element* of `this` has an obvious meaning for `ImList` and `ImShelf`. For
 * `ImSet` and `ImSortedSet` it is the same as:
 *  
 *     this.toArray().[n-1]
 *       
 * ### Examples
 *  
 *     ImList.empty().fold(start, any-function)   =>   start
 * 
 *     Function2<Integer> maxFn = FnFactory.on(Math.class).getFnStatic(int.class, "max", int.class, int.class);
 *      
 *     ImList.onArray(1, 2, 3).fold(0, maxFn)  =>  3
 *      
 * If we have an `add()` method:
 *       
 *     public static int add(int a, int b)
 *     {
 *         return a + b;
 *     }
 *  
 * then we can easily sum the elements in a list:
 *      
 *     Function2<Integer> addFn = FnFactory.on(blah).getFnStatic(int.class, "add", int.class, int.class);
 *      
 *     ImList.onArray(1, 2, 3).fold(0, addFn)  =>  6
 *  
 * To write a text join function (like {@link TextUtils#join})
 *      
 * Using the following two functions (public static fields in {@link FnFactory})
 *
 * - {@link FnFactory#toStringFn} (that refers to {@link Object#toString()})
 * - {@link FnFactory#concatFn} (that refers to {@link String#concat(String)})
 * 
 * we could write:
 * 
 *     public static String joinAlt(ImList<?> list, String separator) throws Exception    
 *     {
 *         if (list.isEmpty())
 *             return "";
 *     
 *         ImList<String> strings = list.map(FnFactory.toStringFn);
 *         
 *         Function1<String> prependSepFn = FnFactory.concatFn.invoke(separator);
 *         return strings.tail().map(prependSepFn).fold(strings.head(), FnFactory.concatFn);
 *     }
 * 
 * and use it like this:
 * 
 *     joinAlt(ImList.onArray(1, 2, 3), ", ")  =>  "1, 2, 3"
 *     joinAlt(ImList.onArray(), ", ")         =>  ""
 *     
 * To calculate the total number of characters in the string representation of objects in a list:
 *  
 *     Function1<Integer> lengthFn = FnFactory.on(String.class).getFn(int.class, "length");
 *  
 *     ImList.onArray(1, 2, 3, 5, 8, 13).map(FnFactory.toStringFn).map(lengthFn).fold(0, addFn)  => 7
 *
 * 
 * ## Currying
 * 
 * ### Introduction
 * 
 * When a language has the concept of first class functions built into it, it allows us to write programs
 * in new ways. Because we can pass functions as arguments to other functions (which are then called
 * higher-order functions), it turns out that we can
 * encapsulate many of what are called patterns in other languages as higher order functions that are parameterised
 * with other functions.
 * 
 * The classic examples of this are the `map()` and `fold()` functions. In fact the concept of mapping and folding is
 * the basis of database map-reduce systems.
 * 
 * It also becomes easy to process
 * functions at run-time in interesting ways that are just not possible otherwise.
 * 
 * For example we can create new functions at run-time by:
 * 
 * * chaining existing functions together
 * * changing the order of arguments of existing functions
 * * supplying an existing function with its first argument
 * 
 * The last example is called *currying*
 * 
 * ### An Example
 * 
 * Let's consider an example. Suppose we want to transform a list of integers by replacing any that are greater than 10 with 10:
 * 
 *     ensureTenOrLess(ImList<Integer> things)
 * 
 * If we use `map()` to do this we need a function of one argument that transforms an integer. We can write such a method
 * using the `min()` method of `Math` with a first argument of `10`:
 *     
 *     public static int tenOrLess(int n)
 *     {
 *         return Math.min(10, n);
 *     }
 *     
 * So - we could extract it as a function and use it like this
 * (assuming that our current class is `Blah`):
 * 
 *     Function1<Integer> tenOrLessFn = FnFactory.on(Blah.class).getFnStatic(int.class, "tenOrLess", int.class);
 *     
 *     fn.toString()  =>  "PackageInfoTest#tenOrLess :: int -> int"
 *     
 *     ImList.onArray(5, 8, 13).map(tenOrLessFn)  =>  [5, 8, 10]
 * 
 * But what if we wanted to generalise this and write a method that took the maximum number as an argument:
 * 
 *     public static ImList<Integer> ensureNOrLess(Integer n, ImList<Integer> things)
 *     
 * What we need is to be able to create **at run-time** a function of one `Integer` argument that will return a number
 * less than or equal to the number `n` - where the value of `n` is known only at run-time.
 * 
 * Given that we can extract the `min()` method from `Math` to get a function which has two arguments:
 * 
 *     static Function2<Integer> minFn = FnFactory.on(Math.class).getFnStatic(int.class, "min", int.class, int.class);
 *     
 *     minFn.toString()  =>  "Math#min :: int -> int -> int"
 *  
 * It would be convenient if we now could just supply it with an argument of
 * `n` and get another function - say `nOrLess(m)` - that just has one argument and will run `minFn` with `n` as the first argument
 * and `m` as the second.
 * 
 * When functions are first class objects,
 * this idea of taking a two-argument function and then creating a one-argument function out of it by fixing its
 * first argument is a common pattern - called currying - and this is exactly what `invoke()` does:
 * 
 *     Function1<Integer> nOrLessFn = minFn.invoke(n);
 * 
 * If `n = 10` then:
 * 
 *     nOrLessFn.toString(), "Math#min 10 :: int -> int"
 *     
 * Now we can use it in `map()`:
 * 
 *     ImList.<Integer> onArray(5, 8, 13).map(nOrLessFn)  =>  [5, 8, 10]
 *    
 * So - given that we have `minFn` defined as above, the method `ensureNOrless()` can be written like this:
 * 
 *     public static ImList<Integer> ensureNOrLess(Integer n, ImList<Integer> things)
 *     {
 *         return things.map(minFn.invoke(n));
 *     }
 * 
 * On a function with n arguments, `invoke(a)` fixes the first argument to be `a` and returns a function with n-1 arguments. On a function
 * with one argument it applies the function to that argument and returns the result.
 * 
 * So there is a sense in which *every* functions with n (n > 1) arguments can be thought of as function of one argument that
 * returns a function of n-1 arguments.
 * 
 * All of this currying business explains the string representation of functions.
 * 
 *     minFn.toString()  =>  "Math#min :: int -> int -> int"
 * 
 * the convention is that the `->` operator associates to the right so no brackets are needed but, if we show them:
 * 
 *     Math#min :: int -> (int -> int)
 *     
 * This makes it even more explicit that this is a function that, when you invoke it with an `int`, will return a function, which,
 * when you invoke it with an `int`, will return an `int`.
 * 
 * The name currying comes from [Haskell Curry][hc] (who, in a nice example of [Stigler's Law Of Eponymy][st],  was
 * apparently not the first person to observe it).
 * 
 * ### Other Java libraries providing first class function features.
 * 
 * There are many other libraries that provide first class functions in various forms.
 * 
 * The ones that come to mind are
 * 
 * * [Jedi] [jedi]
 * * [FunctionalJ] [fj]
 * * [fjava] [fjava]
 * * [Commons Collections] [cc]
 * 
 *
 * ## Some Caveats
 * 
 * The immutable collections library is designed (as the name suggests) to provide immutable collections. The first class
 * functions are just a by-product. First class functions are best used in a proper functional programming
 * language (Haskell, Scala, OCAML etc) and this implementation is not particularly efficient or type safe. 
 * 
 * Ultimately, Java is not a functional programming language and trying to implement a feature like
 * first class functions in it is never going to be totally satisfactory.
 * 
 * One reasonable objection to libraries that introduce fancy-dancy functional features into a non functional language is
 * that it introduces an "impedance mismatch" for the programmers who have to use it. If a Java programmer is not
 * familiar with functional concepts then the extra mental overhead to grasp them in an otherwise non-functional
 * setting may not be worth the effort. If every programmer who comes across some faux functional code is brought
 * to a halt because he can't understand it then, despite the local advantages of the functional style to the cadre
 * of those "in the know",
 * the overall effect on a project could even be detrimental. You have been warned!
 * 
 * Having said all that, we get some value from using them internally and we feel that the ability to
 * use `map()`, `fold()` and other higher-order functions can result in smaller cleaner code
 * so we offer them here in the hope that you might find them useful too.
 * 
 * 
 * [hc]: http://en.wikipedia.org/wiki/Haskell_Curry
 * [st]: http://en.wikipedia.org/wiki/Stigler%27s_law_of_eponymy "Stigler's law of eponymy"
 * [jedi]: http://jedi.codehaus.org/
 * [fj]: http://functionalj.sourceforge.net/
 * [fjava]: http://functionaljava.org/
 * [cc]: http://commons.apache.org/collections/
*/

package immutablecollections.functions;

